import java.util.Stack;

/**
 * Description:
 * User:岁亮亮
 * Date:2025-03-03
 * TIME:19:56
 */
public class Sort {

    //直接插入排序
    public void insertionSort(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            for( int j = i; j >= 0; j--){
                if(j == 0 || key > array[j-1]){
                    array[j] = key;
                    break;
                }
                else {
                    array[j] = array[j-1];
                }
            }


        }
       /* for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(key > array[j]){
                    break;
                }
                else {
                    array[j + 1] = array[j];
                }
            }
            array[j+1] = key;

        }*/
    }
    public void insertionSort2(int[] array){
        //前 n 位是有序的,这里第一个数有序,从第二位开始插入
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] < key){
                    break;
                }
                else{
                    array[j+1] = array[j];
                }
            }
            array[j+1] = key;

        }
    }
    //希尔排序
    public void shellSort(int[] array){
        //设置一个增量,按增量来进行分组排序 ,分组是按每跳过一个增量为一组内的数,直到超过数组的长度
        // 这样可以更大可能的使大的数在后面,小的数在前面.
        int gap = array.length;
        while(gap > 1){
            //然后缩小增量,增量大的时候组内的数少,交换的次数也很少.
            //增量缩小之后,虽然组的的数增多,但之前已经比较交换过,要交换的数也少很多
            //直至增量缩小为1,才开始真正的排序,前面的排序称为预排序,主要是为最后一次做准备,
            // 使大的数在后面,小的数在前面,减小了比较交换的次数,可以看成是对直接插入排序的优化.
            gap = gap / 2;
            insertionSortToShell(gap,array);
        }
    }
    public void insertionSortToShell(int gap,int[] array) {
        for (int i = gap; i < array.length; i++) {
            int key = array[i];
            for (int j = i; j >= 0; j -= gap) {
                if ((j - gap) < 0 || key > array[j - gap]) {
                    array[j] = key;
                    break;
                } else {
                    array[j] = array[j - gap];
                }
            }
        }
    }
    //冒泡排序
    public void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - i -1; j++) {
                if(array[j] > array[j+1]){
                    flag = true;
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            if(!flag){
                break;
            }

        }
    }
    //快速排序
    public void quickSort(int[] array){
        realQuickSortNonR(array,0,array.length - 1);
    }
    private void realQuickSortNonR(int[] array,int left,int right){
        Stack<Integer> stack = new Stack<>();
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            int end = stack.pop();
            int start = stack.pop();
            int pivot = digHole(array,start,end);
            if(pivot > start + 1){
                stack.push(start);
                stack.push(pivot - 1);
            }
            if(pivot + 1 < end){
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    private void realQuickSort(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        int standard = pointer(array,left,right);
        realQuickSort(array,left,standard);
        realQuickSort(array,standard + 1,right);
    }
    private void realQuickSortAndOptimise(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        //快速排序递归到小的区间时不往下进行递归用直接插入排序进行排序 减少递归深度
        if(right - left + 1 <= 15){
            insertionSort2(array);
            return;
        }
        //对基准数进行优化 三数取中法
        int midIndex = middleOfThree(array,left,right);
        swap(array,midIndex,left);
        int standard = pointer(array,left,right);
        realQuickSort(array,left,standard);
        realQuickSort(array,standard + 1,right);
    }
    private int middleOfThree(int[] array,int left,int right){
        int mid = (left + right)/2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }
            else if(array[mid] > array[right]){
                return right;
            }
            else {
                return mid;
            }
        }
        return -1;
    }

    private int patiton(int[] array, int left, int right) {
        int rel = left;
        int pivot = array[left];
        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
            }
            while(left < right && array[left] <= pivot){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,rel,left);
        return left;

    }
    private int digHole(int[] array,int left,int right){
        int rel = left;
        int pivot = array[left];
        while(left < right){
            while(left < right && array[right] >= pivot){
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= pivot){
                left++;
            }
           array[right] = array[left];
        }
        array[left] = pivot;
        return left;
    }
    private int pointer(int[] array,int left,int right){
        int prev = left;
        int cur = left + 1;
        int pivot = array[left];
        while(cur <= right){
            if(array[cur] < pivot && array[++prev] != array[cur]){
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;

    }
    public void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    public static void main(String[] args) {
        Sort sort = new Sort();
        int[] array = new int[]{5,23,12,7,15,24,18,0,29,100,24,1};
        //sort.insertionSort(array);
        //sort.insertionSort(array);
        //sort.bubbleSort(array);
        sort.quickSort(array);
        for(int i : array){
            System.out.println(i);
        }
    }

}
